/**
 * 297. 二叉树的序列化与反序列化
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 */
const { TreeNode, createTreeNode, displayTreeNode } = require('../../libs/public');

const nullValue = -1024;

/**
 * Encodes a tree to a single string.
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  if (!root) {
    return '';
  }
  const buffers = new ArrayBuffer(20000);
  const view = new DataView(buffers);
  let length = 0;
  const stack = new Array(1e4).fill(null);
  let top = 0;
  let bottom = 0;
  let effective = 1;
  stack[top] = root;
  while (top >= bottom) {
    const node = stack[bottom];
    bottom += 1;
    if (node) {
      effective -= 1;
      view.setInt16(length, node.val);
      length += 2;
      top += 1;
      stack[top] = node.left;
      if (node.left) {
        effective += 1;
      }
      top += 1;
      stack[top] = node.right;
      if (node.right) {
        effective += 1;
      }
    } else {
      view.setInt16(length, nullValue);
      length += 2;
    }
    if (effective <= 0) {
      break;
    }
  }
  const charCodes = new Array(length).fill(0);
  for (let i = 0; i < length; i += 1) {
    charCodes[i] = view.getUint8(i);
  }
  return String.fromCharCode(...charCodes);
}

/**
 * Decodes your encoded data to tree.
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  if (!data) return null;
  const { length } = data;
  const buffers = new ArrayBuffer(length);
  const view = new DataView(buffers);
  for (let i = 0; i < length; i += 1) {
    view.setUint8(i, data.charCodeAt(i));
  }
  const stack = new Array(1e4).fill(null);
  let top = 0;
  let bottom = 0;
  const root = new TreeNode(view.getInt16(0));
  stack[top] = root;
  let i = 2;
  let val = 0;
  while (top >= bottom && i < length) {
    const node = stack[bottom];
    bottom += 1;
    val = view.getInt16(i);
    i += 2;
    if (val !== nullValue) {
      node.left = new TreeNode(val);
      top += 1;
      stack[top] = node.left;
    }
    if (i >= length) {
      break;
    }
    val = view.getInt16(i);
    i += 2;
    if (val !== nullValue) {
      node.right = new TreeNode(val);
      top += 1;
      stack[top] = node.right;
    }
  }
  return root;
}

console.log(displayTreeNode(deserialize(serialize(createTreeNode([1, 2, 3, null, null, 4, 5])))) === '[1,2,3,null,null,4,5]');
console.log(displayTreeNode(deserialize(serialize(createTreeNode([])))) === '[]');
